package com.lie.prepare.sort;

import org.junit.Test;

import static com.lie.prepare.sort.util.MyArrayHelper.getArray;
import static com.lie.prepare.sort.util.MyArrayHelper.printArraySort;

/**
 * Created by lie on 2018/4/18.
 */
public class QuickSort {
    private static int findMid(int[] array, int left, int right){
        int indexMid = left;
        int p = array[right];

        for (int i = left ; i < right; i++) {
            if (array[i] < p) {
                int temp = array[i];
                array[i] = array[indexMid];
                array[indexMid] = temp;
                indexMid++;
            }
        }

        array[right]  = array[indexMid];
        array[indexMid] = p;
        return indexMid;
    }
    private static void divide(int[] array, int left, int right){
        if (left < right) {
            int mid = findMid(array, left, right);
            divide(array, left, mid-1);
            divide(array, mid+1, right);
        }
    }

    public static void sort(int[] array){
        divide(array, 0, array.length-1);
    }

    @Test
    public void test(){
        int[] array = getArray();
        sort(array);
        printArraySort(array);
    }
}
